package com.berchen.数据结构.递归;

/**
 * 迷宫问题
 *
 * 8*7 的迷宫 一周都是墙
 * 1 1 1 1 1 1 1
 * 1 0 0 0 0 0 1
 * 1 0 0 0 0 0 1
 * 1 1 1 0 0 0 1
 * 1 0 0 0 0 0 1
 * 1 0 0 0 0 0 1
 * 1 0 0 0 0 0 1
 * 1 1 1 1 1 1 1
 *
 * 需要从 [1 1 ] 走到 [6 5]
 *
 * 找到迷宫中打一条出路
 * 制定一个策略：上 右 下 左
 * 策略不同路线不同  路线长度就不同 如果需要找到最短路线 就需要所有策略找到所有路线 然后进行比较长短
 *
 * 1 代表墙 2 代表可以通  3 代表不通  0 代表没有接触过
 */
public class Maze {

    /**
     *
     * @param map 目标迷宫
     * @param i 起点 i
     * @param j 起点
     * @param m 终点
     * @param n 终点
     * @return
     */
    public boolean getWay(int[][] map,int i ,int j ,int m,int n ){

        if(map[m][n]==2){   // 找到路线了
            return true;
        }
        if(map[i][j]==0) {  // 该点还没有走过
            map[i][j] = 2;  // 假设该点能走通
            if (getWay(map,i-1,j,m,n)){ // 往上走 看上面那个点能否走通
                return true;
            }else if(getWay(map,i,j+1,m,n)){
                return true;
            }
            else if(getWay(map,i+1,j,m,n)){
                return true;
            }else if (getWay(map,i,j-1,m,n)){
                return true;
            }
            else {
                map[i][j]=3;
                return false;
            }
        }
        else {  // 1 2 3 三种都不行
            return  false;
        }
    }
}
